package com.leetcode.offer.chapter5;

import java.util.Collections;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dennis Li
 * @date 2020/7/18 10:35
 */
public class MaxSlidingWindow_59 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0) return new int[0];
        // 这里通过LinkedList实现双端队列
        LinkedList<Integer> list = new LinkedList<>();
        int[] ans = new int[nums.length - k + 1];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            // 当队列小于k时，先执行初始化
            if (list.size() < k) {
                list.add(nums[i]);
                max = Math.max(max, nums[i]);
                continue;
            }
            // 记录最大值
            ans[i - k] = max;
            // 最大值不在队首,说明还在滑动窗口内部，不需要遍历整个窗口更新
            // 只需要与新加入的值比较
            if (max != list.peekFirst()) {
                max = Math.max(max, nums[i]);
                list.pollFirst();
                list.add(nums[i]);
            } else if (max == list.peekFirst()) {
                // 最大值在队首，需要出队
                list.pollFirst();
                list.add(nums[i]);
                // 遍历找到最大值
                max = Collections.max(list);
            }
        }
        // 好像少了一位
        ans[nums.length - k] = max;
        return ans;
    }

    public int[] maxSlidingWindow2(int[] nums, int k) {
        // 单调队列
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 不一定要严格遵守空间大小为k的约定
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.pollFirst(); // 删除 deque 中对应的 nums[i-1]
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.pollLast(); // 保持 deque 递减
            deque.offerLast(nums[j]);
            // 当i>=0，说明队列执行完了初始化
            if(i >= 0)
                res[i] = deque.peekFirst();  // 记录窗口最大值
        }
        return res;
    }



}
